package com.bit.stack;

import java.util.Stack;

public class StackProblem {

    //给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
    public boolean isValid(String s) {
        Stack<Character> stack=new Stack<>();
        //针对字符串进行遍历，取出每个字符
        for (int i=0;i<s.length();i++){
            char c=s.charAt(i);
            //如果是左括号，就入栈
            if (c=='('||c=='{'||c=='['){
                stack.push(c);
                continue;
            }
            //如果是右括号，就判断栈顶元素是否匹配
            if (c==')'||c=='}'||c==']'){
                if (stack.isEmpty()){
                    // 如果栈为空, 无法取栈顶的.
                    // 由于当前读到了一个右括号, 要求必须得在栈里有一个匹配的左括号.
                    // 但是栈是空的, 说明没有匹配的左括号, 直接返回 false.
                    return false;
                }
                // 栈不为空, 取出栈顶元素
                char top=stack.pop();
                // 判断栈顶元素是否匹配
                if (top=='['&&c==']'){
                    continue;
                }
                if (top=='{'&&c=='}'){
                    continue;
                }
                if (top=='('&&c==')'){
                    continue;
                }
                //其他情况，匹配失败
                return false;
            }
        }
        // 整个循环结束, 再来检查栈是否为空.
        // 如果栈为空, 说明所有括号都匹配成功.
        // 如果栈不为空, 说明还有未匹配的左括号.
        if (stack.isEmpty()){
            return true;
        }
        return false;
    }

    //输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。
    public boolean IsPopOrder (int[] pushA, int[] popA) {
        Stack<Integer> stack=new Stack<>();
        //2.针对pushA进行遍历
        int pushIndex = 0;
        int popIndex = 0;
        for (;pushIndex<pushA.length;pushIndex++) {
            // 3. 把当前的 pushIndex 指向的元素入栈.
            stack.push(pushA[pushIndex]);
            // 4. 拿着 popA 的当前元素和栈顶进行比较. 循环比较的过程. 只要比较成功, 出栈, 并且进行下次循环,
            //    也就是比较 popA 的下一个元素和栈顶的关系.
            while(!stack.isEmpty()&&stack.peek()==popA[popIndex]){
                stack.pop();
                popIndex++;
            }
            // 上述条件不匹配, 说明当前 popIndex 指向的元素, 和栈顶元素不同的.
            // 就需要再次入栈新的元素, 找新的机会.
            // 此处就结束循环进入下次即可.
        }
        // 5. 当整个 pushA 遍历完毕, 说明 "所有的机会" 都用完了.
        //    此时如果栈已经是空了, 说明前面 popA 的元素就都匹配成功; 如果栈非空, 还有 popA 的元素是无法匹配的.
        if (stack.isEmpty()){
            return true;
        }
        return false;
    }

//给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
    public int evalRPN(String[] tokens) {
            Stack<Integer> stack=new Stack<>();
        // 2. 遍历 tokens, 取出每个元素.
        for (String token : tokens){
            // 3. 判定 token 是数字
            if (isNumber(token)){
                stack.push(Integer.parseInt(token));
                continue;
            }
            // 4. 判定 token 是运算符
            //    出栈两个元素. 先出栈的是第二个操作数, 后出栈的是第一个操作数.
            int num2 = stack.pop();
            int num1 = stack.pop();
            // 5. 判定当前的运算符是哪个, 进行运算, 把得到的结果, 重新入栈.
            if (token.equals("+")) {
                stack.push(num1 + num2);
            } else if (token.equals("-")) {
                stack.push(num1 - num2);
            } else if (token.equals("*")) {
                stack.push(num1 * num2);
            } else if (token.equals("/")) {
                stack.push(num1 / num2);
            }
        }
        return stack.pop();
    }
    private static boolean isNumber(String token){
        // 如果 token 是运算符, 就返回 false, 否则返回 true.
        if (token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/")) {
            return false;
        }
        return true;
    }
}
